package org.example;

import java.util.ArrayList;
import java.util.List;

public class Test2 {
    //leetcode 37 解数独 https://leetcode.cn/problems/sudoku-solver/description/
//    public boolean[][] vis1, vis2,vis3;
    public void solveSudoku1(char[][] board) {
        vis1 = new boolean[9][10];
        vis2 = new boolean[9][10];
        vis3 = new boolean[9][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    vis1[i][num] = vis2[j][num] =  vis3[i / 3 * 3 + j / 3][num] = true;
                }
            }
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    backtracking(board,i,j);
                    break;
                }
            }
        }
    }

    public void backtracking1(char[][] board, int cow,int row) {
        for (int i = row; i < 9; i++) {
            if (board[cow][i] == '.') {
                for (int j = 1; j <= 9; j++) {
                    if (!vis1[cow][j] && !vis2[i][j] && !vis3[cow / 3 * 3 + i / 3][j]) {
                        board[cow][i] = (char)(j + '0');
                        vis1[cow][j] = vis2[i][j] = vis3[cow / 3 * 3 + i / 3][j] = true;
                        if (i == 8) {
                            backtracking(board,cow + 1,0);
                        }else {
                            backtracking(board,cow,row + 1);
                        }
                        board[cow][i] = '.';
                        vis1[cow][j] = vis2[i][j] = vis3[cow / 3 * 3 + i / 3][j] = false;
                    }
                }
            }
        }
    }

    public boolean[][] vis1, vis2, vis3;

    public void solveSudoku(char[][] board) {
        vis1 = new boolean[9][10];
        vis2 = new boolean[9][10];
        vis3 = new boolean[9][10];

        // Initialize the vis arrays
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    vis1[i][num] = vis2[j][num] = vis3[i / 3 * 3 + j / 3][num] = true;
                }
            }
        }

        // Start backtracking from the first cell
        backtracking(board, 0, 0);
    }

    public boolean backtracking(char[][] board, int row, int col) {
        if (row == 9) return true; // If we reached the end of rows, the board is solved

        // If we reached the end of columns, move to the next row
        if (col == 9) return backtracking(board, row + 1, 0);

        // If the cell is already filled, move to the next cell
        if (board[row][col] != '.') return backtracking(board, row, col + 1);

        // Try placing digits from 1 to 9
        for (int num = 1; num <= 9; num++) {
            if (!vis1[row][num] && !vis2[col][num] && !vis3[row / 3 * 3 + col / 3][num]) {
                board[row][col] = (char) (num + '0');
                vis1[row][num] = vis2[col][num] = vis3[row / 3 * 3 + col / 3][num] = true;

                // Move to the next cell
                if (backtracking(board, row, col + 1)) return true;

                // Undo the move
                board[row][col] = '.';
                vis1[row][num] = vis2[col][num] = vis3[row / 3 * 3 + col / 3][num] = false;
            }
        }

        return false; // No valid number found, backtrack
    }



    public static void main(String[] args) {
        List<String[]> list = new ArrayList<>();
        list.add(new String[]{"5","3",".",".","7",".",".",".","."});
        list.add(new String[]{"6",".",".","1","9","5",".",".","."});
        list.add(new String[]{".","9","8",".",".",".",".","6","."});
        list.add(new String[]{"8",".",".",".","6",".",".",".","3"});
        list.add(new String[]{"4",".",".","8",".","3",".",".","1"});
        list.add(new String[]{"7",".",".",".","2",".",".",".","6"});
        list.add(new String[]{".","6",".",".",".",".","2","8","."});
        list.add(new String[]{".",".",".","4","1","9",".",".","5"});
        list.add(new String[]{".",".",".",".","8",".",".","7","9"});
        char[][] board = new char[9][9];
        int index = 0;
        for (String[] s : list) {
            for (int i = 0; i < 9; i++) {
                board[index][i] = s[i].charAt(0);
            }
            index++;
        }
        Test2 test2 = new Test2();
        test2.solveSudoku(board);
        System.out.println(777);
    }
}
